// https://www.lintcode.com/problem/longest-palindromic-substring/my-submissions

class Solution {
public:
    /**
     * @param s: input string
     * @return: the longest palindromic substring
     */
    
    // 法一：双循环
    // bool isPalin(string s)
    // {
    //     for (int i = 0; i < s.length() / 2; ++i)
    //     {
    //         if (s[i] != s[s.length() - i - 1]) return false;
    //     }
    //     return true;
    // }
    
    // string longestPalindrome(string &s) {
    //     int maxLen = 1;
    //     string maxStr = "";
    //     if (s.length() <= 1) return s;
    //     for (int i = 0; i < s.length(); ++i)
    //     {
    //         for (int j = i + 1; j < s.length(); ++j)
    //         {
    //             int len = j - i + 1;
    //             string subStr = s.substr(i, len);
    //             if (isPalin(subStr) && len > maxLen)
    //             {
    //                 maxLen = len;
    //                 maxStr = subStr;
    //             }
    //         }
    //     }
    //     return maxStr;
    // } 
    
    // 法二：从中心扩散，注意处理以一个字母为中心和以两个相同字母为中心的情况
    // string getPalin(string s, int i, int j)
    // {
    //     while (i >= 0 && j < s.length()) 
    //     {
    //         if (s[i] != s[j]) break;
    //         i--;
    //         j++;
    //     }
    //     i++;
    //     return s.substr(i, j - i);
    // }
    // string longestPalindrome(string &s) {
    //     if (s.length() <= 1) return s;
    //     string maxStr = "";
    //     for (int i = 1; i < s.length(); ++i)
    //     {
    //         string a = getPalin(s, i, i);
    //         if (s[i] == s[i - 1]) 
    //         {
    //             string b = getPalin(s, i - 1, i);
    //             if (b.length() > a.length() && b.length() > maxStr.length()) 
    //                 maxStr = b;
    //         }
    //         if (a.length() > maxStr.length()) maxStr = a;
    //     }
    //     return maxStr;
    // }
    
    // Longest Palindromic Substring 的全部算法及时间复杂度
    // 动态规划 Dynamic Programming - O(n^2) // 必须掌握
    // 枚举法 Enumeration - O(n^2) // 必须掌握
    // 后缀数组 Suffix Array - O(n) // 完全不用学
    // Manacher’s Algorithm - O(n) // 学有余力可以阅读全文并背诵
    
    // follow up:不能枚举中心点
    // 基于动态规划的算法，时间复杂度 O(n^2)，但是会耗费额外的 O(n^2) 的空间复杂度
    string longestPalindrome(string &s) {
        if (s.empty() || s.length() == 1)
            return s;
        int n = s.length();
        vector<vector<bool>> isPalin(n, vector<bool>(n));
        int longest = 1;
        int start = 0;
        for (int i = 0; i < n; ++i)
        {
            isPalin[i][i] = true;
        }
        for (int i = 0; i < n - 1; ++i)
        {
            isPalin[i][i + 1] = (s[i] == s[i + 1]);
            if (isPalin[i][i + 1])
            {
                longest = 2;
                start = i;
            }
        }
        for (int len = 3; len <= n; ++len)
        {
            for (int i = 0; i < n - len + 1; ++i)
            {
                isPalin[i][i + len - 1] = isPalin[i + 1][i + len - 2] && (s[i] == s[i + len - 1]);
                if (isPalin[i][i + len - 1] && len > longest)
                {
                    longest = len;
                    start = i;
                }
            }
        }
        return s.substr(start, longest);
    }
};
